package algorithm.leetcode.medium;

/*
 对链表进行插入排序。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/4
 */
public class Question147 {

    public static void main(String[] args) {

    }

    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode tempHead = new ListNode(0);
        tempHead.next = head;

        ListNode cur = head;
        ListNode pre;
        ListNode temp;

        while (cur.next != null) {
            if (cur.val <= cur.next.val) {
                // 前一项小于后一项
                cur = cur.next;
            }else {
                temp = cur.next;
                cur.next = cur.next.next;

                pre = tempHead;
                //  插入排序核心思想 在有序列表中查找合适的位置
                while (pre.next.val <= temp.val) {
                    pre =pre.next;
                }
                temp.next = pre.next;
                pre.next = temp;
            }
        }
        return tempHead.next;
    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
